{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Fair Distribution of Cookies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: distributeCookies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #公平分发饼干"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>cookies</code> ，其中 <code>cookies[i]</code> 表示在第 <code>i</code> 个零食包中的饼干数量。另给你一个整数 <code>k</code> 表示等待分发零食包的孩子数量，<strong>所有</strong> 零食包都需要分发。在同一个零食包中的所有饼干都必须分发给同一个孩子，不能分开。</p>\n",
    "\n",
    "<p>分发的 <strong>不公平程度</strong> 定义为单个孩子在分发过程中能够获得饼干的最大总数。</p>\n",
    "\n",
    "<p>返回所有分发的最小不公平程度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>cookies = [8,15,10,20,8], k = 2\n",
    "<strong>输出：</strong>31\n",
    "<strong>解释：</strong>一种最优方案是 [8,15,8] 和 [10,20] 。\n",
    "- 第 1 个孩子分到 [8,15,8] ，总计 8 + 15 + 8 = 31 块饼干。\n",
    "- 第 2 个孩子分到 [10,20] ，总计 10 + 20 = 30 块饼干。\n",
    "分发的不公平程度为 max(31,30) = 31 。\n",
    "可以证明不存在不公平程度小于 31 的分发方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>cookies = [6,1,3,2,2,4,1,2], k = 3\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>一种最优方案是 [6,1]、[3,2,2] 和 [4,1,2] 。\n",
    "- 第 1 个孩子分到 [6,1] ，总计 6 + 1 = 7 块饼干。 \n",
    "- 第 2 个孩子分到 [3,2,2] ，总计 3 + 2 + 2 = 7 块饼干。\n",
    "- 第 3 个孩子分到 [4,1,2] ，总计 4 + 1 + 2 = 7 块饼干。\n",
    "分发的不公平程度为 max(7,7,7) = 7 。\n",
    "可以证明不存在不公平程度小于 7 的分发方案。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= cookies.length &lt;= 8</code></li>\n",
    "\t<li><code>1 &lt;= cookies[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>2 &lt;= k &lt;= cookies.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [fair-distribution-of-cookies](https://leetcode.cn/problems/fair-distribution-of-cookies/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [fair-distribution-of-cookies](https://leetcode.cn/problems/fair-distribution-of-cookies/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,15,10,20,8]\\n2', '[6,1,3,2,2,4,1,2]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCookies(self, cookies: List[int], k: int) -> int:\n",
    "        sz = len(cookies)\n",
    "        if sz <= k:\n",
    "            return max(cookies)\n",
    "        result = [float(\"inf\")]\n",
    "        distribution = [0] * k\n",
    "        def dfs(start):\n",
    "            if start >= sz:\n",
    "                result[0] = min(result[0], max(distribution))\n",
    "            else:\n",
    "                element = cookies[start]\n",
    "                for i in range(k):\n",
    "                    distribution[i] += element\n",
    "                    dfs(start + 1)\n",
    "                    distribution[i] -= element\n",
    "        dfs(0)\n",
    "        return result[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCookies(self, cookies: List[int], k: int) -> int:\n",
    "        # 一共有这么多个饼干\n",
    "        # 一共有这么多孩子\n",
    "        # 初始状态下，所有的孩子都没有饼干\n",
    "        kid_cookies = [0] * k\n",
    "        n = len(cookies)\n",
    "        ans = sum(cookies)\n",
    "\n",
    "        #将第i个饼干分配给哪个孩子能最小不公平程度\n",
    "        def back_trace(index,total):\n",
    "            nonlocal ans\n",
    "            # 循环的是将这个饼干分给某个孩子\n",
    "            # 更新答案\n",
    "            if index == n:\n",
    "                #print(total)\n",
    "                ans = min(total,ans)\n",
    "                return\n",
    "            for i in range(k):\n",
    "                # 这个剪枝加快速度100倍\n",
    "                if i > 0 and kid_cookies[i] == kid_cookies[i-1]:\n",
    "                    continue\n",
    "                kid_cookies[i] += cookies[index]\n",
    "                back_trace(index + 1, max(total,kid_cookies[i]))\n",
    "                kid_cookies[i] -= cookies[index]\n",
    "        back_trace(0,0)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCookies(self, cookies: List[int], k: int) -> int:\n",
    "        # 一共有这么多个饼干\n",
    "        # 一共有这么多孩子\n",
    "        # 初始状态下，所有的孩子都没有饼干\n",
    "        kid_cookies = [0] * k\n",
    "        n = len(cookies)\n",
    "        ans = sum(cookies)\n",
    "\n",
    "        #将第i个饼干分配给哪个孩子能最小不公平程度\n",
    "        def back_trace(index,total):\n",
    "            nonlocal ans\n",
    "            # 循环的是将这个饼干分给某个孩子\n",
    "            # 更新答案\n",
    "            if index == n:\n",
    "                #print(total)\n",
    "                ans = min(total,ans)\n",
    "                return\n",
    "            for i in range(k):\n",
    "                # 这个剪枝加快速度100倍\n",
    "                if i > 0 and kid_cookies[i] == kid_cookies[i-1]:\n",
    "                    continue\n",
    "                kid_cookies[i] += cookies[index]\n",
    "                back_trace(index + 1, max(total,kid_cookies[i]))\n",
    "                kid_cookies[i] -= cookies[index]\n",
    "        back_trace(0,0)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCookies(self, cookies: List[int], k: int) -> int:\n",
    "        m = 1 << len(cookies)\n",
    "        SUM = [0] * m\n",
    "        for i in range(m):\n",
    "            cur = 0\n",
    "            for j in range(len(cookies)):\n",
    "                if i & 1 << j:\n",
    "                    cur += cookies[j]\n",
    "            SUM[i] = cur\n",
    "\n",
    "        f = SUM.copy()\n",
    "        for _ in range(1, k):\n",
    "            for j in range(m - 1, 0, -1):\n",
    "                s = j\n",
    "                while s:\n",
    "                    v = f[j ^ s]\n",
    "                    if SUM[s] > v: v = SUM[s]  # 不要用 max 和 min，那样会有额外的函数调用开销\n",
    "                    if v < f[j]: f[j] = v\n",
    "                    s = (s - 1) & j\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCookies(self, cookies: List[int], k: int) -> int:\n",
    "        def bt(state, k):\n",
    "            base = state\n",
    "            state = (state - 1) & base\n",
    "            while state:\n",
    "                path.append(dp[state])\n",
    "                if k:\n",
    "                    bt(base ^ state, k - 1)\n",
    "                else:\n",
    "                    path.append(dp[base ^ state])\n",
    "                    self.ans = min(self.ans, max(path))\n",
    "                    path.pop()\n",
    "                state = (state - 1) & base\n",
    "                path.pop()\n",
    "\n",
    "        n = len(cookies)\n",
    "        dp = [0] * (1 << n)\n",
    "        for i in range(1 << n):\n",
    "            dp[i] = sum((i >> k & 1) * cookies[k] for k in range(n))\n",
    "        path = []\n",
    "        self.ans = inf\n",
    "        bt((1 << n) - 1, k - 2)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCookies(self, cookies: List[int], k: int) -> int:\n",
    "        l = len(cookies)\n",
    "        @cache\n",
    "        def df(s, k):\n",
    "            \n",
    "            if s.bit_count() == l:\n",
    "                # print(bin(s)[2:].zfill(l), k, 0)\n",
    "                return 0\n",
    "            if l - s.bit_count() <= k:\n",
    "                t = []\n",
    "                for i in range(l):\n",
    "                    if s >> i & 1 == 0:\n",
    "                        t.append(cookies[i])\n",
    "                # print(bin(s)[2:].zfill(l), k, max(t + [0]))\n",
    "                return max(t + [0])\n",
    "            if k == 1:\n",
    "                t = 0\n",
    "                for i in range(l):\n",
    "                    if s >> i & 1 == 0:\n",
    "                        t += cookies[i]\n",
    "\n",
    "                return t\n",
    "            res = float('inf')\n",
    "            for x in range(2 ** l):\n",
    "                if x & s == 0:\n",
    "                    t = 0\n",
    "                    for i in range(l):\n",
    "                        if x >> i & 1 == 1:\n",
    "                            t += cookies[i]\n",
    "                    # print(t)\n",
    "                    res = min(res, max(t, df(x | s, k - 1)))\n",
    "            # print(bin(s)[2:].zfill(l), k, res)\n",
    "            return res\n",
    "        return df(0, k)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCookies(self, cs: List[int], k: int) -> int:\n",
    "        n = len(cs)\n",
    "        mask = 1 << n\n",
    "\n",
    "        g = [0] * mask\n",
    "        for s in range(mask):\n",
    "            t = 0\n",
    "            # 对某个s来说，如果这一位是1，就加对应的值\n",
    "            for i in range(n):\n",
    "                if s >> i & 1:\n",
    "                    t += cs[i]\n",
    "            g[s] = t\n",
    "        \n",
    "        f = [[inf] * mask for _ in range(k+1)]\n",
    "        f[0][0] = 1\n",
    "\n",
    "        for i in range(1, k+1):\n",
    "            for s in range(mask):\n",
    "                p = s\n",
    "                while p != 0:\n",
    "                    f[i][s] = min(f[i][s], max(f[i-1][s-p], g[p]))\n",
    "                    p = (p - 1) & s\n",
    "        \n",
    "        return f[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCookies(self, cs: List[int], k: int) -> int:\n",
    "        n, mask, INF = len(cs), 1 << len(cs), 0x3f3f3f3f\n",
    "        g = [0] * mask\n",
    "        for s in range(mask):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += cs[i] if (s >> i) & 1 == 1 else 0\n",
    "            g[s] = t\n",
    "        f = [[INF] * mask for _ in range(k + 10)]\n",
    "        f[0][0] = 0\n",
    "        for i in range(1, k + 1):\n",
    "            for s in range(mask):\n",
    "                p = s\n",
    "                while p != 0:\n",
    "                    f[i][s] = min(f[i][s], max(f[i - 1][s - p], g[p]))\n",
    "                    p = (p - 1) & s\n",
    "        return f[k][mask - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distributeCookies(self, a: List[int], k: int) -> int:\n",
    "        # 暴力，但压缩状态（状态压缩 dp）\n",
    "        # 前 i 个人划分的状态是 j, 存储值为最小的 最大不公平程度\n",
    "        # 每块饼干是否分发，所以一共 2**n 种状态\n",
    "        \n",
    "        \n",
    "        n = len(a)\n",
    "        n2 = 2**n\n",
    "        # 预计算每种状态的饼干数\n",
    "        cnt = [0 for _ in range(n2)]\n",
    "        for s in range(n2):\n",
    "            cur = 0\n",
    "            for i in range(n):\n",
    "                if s &(1<<i):\n",
    "                    cur += a[i]\n",
    "            cnt[s] = cur\n",
    "\n",
    "        dp = [[inf]*n2 for _ in range(k+1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, k+1):\n",
    "            # 枚举每种状态、下一种状态 不好写\n",
    "            # 可以枚举 下一种状态，前一状态，因为下一种状态一定是包含前一状态的，有简便写法\n",
    "            # 枚举 下一种状态\n",
    "            for s in range(n2):\n",
    "                tot = cnt[s] # 下一种状态的所有已经分发的饼干数目\n",
    "                ps = s # 暂存\n",
    "                while ps:\n",
    "                    ps = (ps-1)&s\n",
    "                    pcnt = cnt[ps]\n",
    "                    dp[i][s] = min(dp[i][s], max(tot-pcnt, dp[i-1][ps]))\n",
    "        return dp[k][n2-1]\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
